package 三数之和;

//给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
//
//注意：答案中不可以包含重复的三元组。
//输入：nums = [-1,0,1,2,-1,-4]
//输出：[[-1,-1,2],[-1,0,1]]
//解释：
//nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
//nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
//nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
//不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
//注意，输出的顺序和三元组的顺序并不重要。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution
{
    public List<List<Integer>> threeSum(int[] nums)
    {
        //笨方法，三层循环找是否等于0
        //双指针法，实际上是三指针法，外层一个first，内部是求两数之和的思路
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int first = 0; first < n; first++)
        {
            //跳过重复的数
            if (first > 0 && nums[first] == nums[first - 1])
                continue;
            //c指针在最右端
            int third = n - 1;
            int target = -nums[first];//目标值
            for (int second = first + 1; second < n; second++)
            {
                //跳过重复值
                if (second > first + 1 && nums[second] == nums[second - 1])
                    continue;
                //保证b的指针在c指针的左侧
                while (second < third && nums[second] + nums[third] > target)
                    third--;
                //当bc指针碰撞，b继续增大一定不会满足条件，可以直接跳出循环
                if (second == third)
                    break;
                if (nums[second] + nums[third] == target)
                {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }

    //[-1,0,1,2,-1,-4]
    //[-4,-1,-1,0,1,2]
    public static List<List<Integer>> threeSum0(int[] nums)
    {
        ArrayList<List<Integer>> lists = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);
        for (int first = 0; first < nums.length; first++)
        {
            int target = -nums[first];
            //先不考虑重复
            //考虑重复
            //跳过重复的数，搞不出来，下一个一样搞不出来
            if (first > 0 && nums[first] == nums[first - 1])
                continue;
            int third = n - 1;
            for (int second = first + 1; second < n; second++)
            {
                //去除重复
                if(second>first+1&&nums[second]==nums[second-1])
                    continue;
                while (second < third && nums[second] + nums[third] > target)
                    third--;
                //second和third指针碰撞的情况
                if (second==third)
                    break;
                //满足条件
                if (nums[second] + nums[third] == target)
                {
                    List<Integer> list = Arrays.asList(nums[first], nums[second], nums[third]);
                    lists.add(list);
                }

            }
        }
        return lists;
    }

    public static void main(String[] args)
    {
        int[] nums={0,0,0,0};
        System.out.println(threeSum0(nums));
    }
}
